package two.chapter_4.c4_2;

public class KosarajuSCC {

    private boolean[] marked;
    private int[] id;//强连通分量标识符
    private int count;//强连通分量的数量

    public KosarajuSCC(Digragh g){
        marked=new boolean[g.v()];
        id=new int[g.v()];
        //反向图中进行深度优先搜索
        DepthFirstOrder order=new DepthFirstOrder(g.reverse());
        //反向图的逆后续迭代
        for (int s:order.postReverse()){
            if (!marked[s]){
                dfs(g,s);//原始图中进行深度优先搜索
                count++;
            }
        }
    }

    private void dfs(Digragh g, int v) {
        marked[v]=true;
        id[v]=count;
        for (int w:g.adj(v)){
            if (!marked[w])
                dfs(g,w);
        }
    }
    public boolean stronglyConnected(int v,int w){
        return id[v]==id[w];
    }
    public int id(int v){
        return id[v];
    }

    public int count(){
        return count;
    }
}
